//dynamic bit array
//$Id: dynamic_bit_array.h 670 2011-02-27 11:52:14Z Oleg.Bulychov $
#pragma once

#if defined(_MSC_VER)
#include <intrin.h>
#endif

#include "src/heo/include/alloc_big.h"
#include "src/heo/include/reflection.h"

//:undef if no bsfl
#define USE_ASM_BSFL

template<int size_of_size_t>
struct First_bit;

template<>
struct First_bit<4>
{
    static inline int find(size_t n)
    {
#if defined(_MSC_VER) && !defined(_DEBUG)
        unsigned long r;
        _BitScanForward(&r, (unsigned long)n);
        return r;
#elif defined(__GNUC__) && defined(USE_ASM_BSFL)
        int r;
        asm volatile(" bsfl %1, %0": "=r"(r): "rm"(n) );
        return r;
#else
        n ^= n-1;
        int r = 0;
        if( n >= 1ul << 16 ) { n >>= 16; r  =16; }
        if( n >= 1ul <<  8 ) { n >>=  8; r += 8; }
        if( n >= 1ul <<  4 ) { n >>=  4; r += 4; }
        if( n >= 1ul <<  2 ) { n >>=  2; r += 2; }
        if( n >= 1ul <<  1 ) {           r += 1; }
        return r;
#endif
    }
};

template<>
struct First_bit<8>
{
    static inline int find(size_t n)
    {
#if defined(_MSC_VER) && !defined(_DEBUG) && defined(_WIN64)
        unsigned long r;
        _BitScanForward64(&r, n);
        return r;
#elif defined(__GNUC__) && defined(USE_ASM_BSFL)
        int r;
        asm volatile(" bsfl %1, %0": "=r"(r): "rm"(n) );
        return r;
#else
        n ^= n-1;
        int r = 0;
        if( n >= 1ull << 32 ) { n >>= 32; r  = 32; }
        if( n >= 1ull << 16 ) { n >>= 16; r += 16; }
        if( n >= 1ull <<  8 ) { n >>=  8; r +=  8; }
        if( n >= 1ull <<  4 ) { n >>=  4; r +=  4; }
        if( n >= 1ull <<  2 ) { n >>=  2; r +=  2; }
        if( n >= 1ull <<  1 ) {           r +=  1; }
        return r;
#endif
    }
};


template<typename SizeType = size_t, typename BlockType = size_t>
class dynamic_bit_array
{
public:
    typedef SizeType  size_type;
    typedef BlockType block_type;
    typedef mem_util::TFloHeader* PFloHeader;
    enum
    {
        bits_per_block = 8 * sizeof(block_type),
    };
    static const size_type npos = size_type(-1);

    block_type** pp_;
    size_type size_;

    dynamic_bit_array(): pp_(), size_()
    {}

    explicit dynamic_bit_array(dynamic_bit_array const& right): pp_(), size_()
    {
        if (right.size_)
        {
            pp_ = big_allocator::AllocT<block_type>(right.block_count(), 0, false);
            memcpy(*pp_, *right.pp_, right.cb_size());
            size_ = right.size_;
        }
    }

    ~dynamic_bit_array()
    {
        big_allocator::FreeT(pp_);
    }

    void swap(dynamic_bit_array& right)
    {
        std::swap(pp_, right.pp_);
        std::swap(size_, right.size_);
    }

    dynamic_bit_array& operator=(dynamic_bit_array const& right)
    {
        if (this != &right)
        {
            dynamic_bit_array<size_type, block_type> tmp(right);
            tmp.swap(*this);
        }
        return *this;
    }

    void resize(size_type size, size_type reserved = 0, bool zero_init = true)
    {
        size_t new_size = (size + bits_per_block - 1) / bits_per_block;
        size_t new_reserved = (reserved + bits_per_block - 1) / bits_per_block;
        if (pp_)
            big_allocator::ReallocT(*pp_, new_size, new_reserved, zero_init);
        else
            pp_ = big_allocator::AllocT<block_type>(new_size, new_reserved, zero_init);
        size_ = size;
    }

    size_t cb_size() const { return PFloHeader(*pp_)[-1].data_size_; }

    size_type block_count() const
    {
        return size_type(cb_size() / sizeof(block_type));
    }

    size_type* front_block() { return *pp_; } 

    size_type size() const
    {
        return size_;
    }

    bool bad_Index(size_type pos) const
    {
        return pos >= size_;
    }

    void set()
    {
        memset(*pp_, 0xFF, cb_size());
        if (size_ % bits_per_block)
        {
            (*pp_)[size_ / bits_per_block] &= ~(block_type)0 >> (bits_per_block - size_ % bits_per_block);
        }
    }

    void set(size_type pos)
    {
        ASSERT_(!bad_Index(pos));
        (*pp_)[pos / bits_per_block] |= (block_type)1 << pos % bits_per_block;
    }

    void set(size_type pos, bool value)
    {
        ASSERT_(!bad_Index(pos));
        if (value)
            (*pp_)[pos / bits_per_block] |= (block_type)1 << pos % bits_per_block;
        else
            (*pp_)[pos / bits_per_block] &= ~((block_type)1 << pos % bits_per_block);
    }

    bool get(size_type pos) const
    {
        ASSERT_(!bad_Index(pos));
        return ((*pp_)[pos / bits_per_block] & ((block_type)1 << pos % bits_per_block)) != 0;
    }

    void clear(size_type pos)
    {
        ASSERT_(!bad_Index(pos));
        (*pp_)[pos / bits_per_block] &= ~((block_type)1 << pos % bits_per_block);
    }

    size_type find_from(size_type i) const
    {
        for (size_type count = block_count(); i < count; ++i)
        {
            if (block_type t = (*pp_)[i])
            {
                return i * bits_per_block + First_bit<sizeof(t)>::find(t);
            }
        }
        return npos;
    }

    size_type find_first() const
    {
        return find_from(0);
    }

    size_type find_next(size_type prev) const
    {
        ASSERT_(!bad_Index(prev));
        ++prev;
        if (prev >= size_)
            return npos;
        size_type block_index = prev / bits_per_block;
        block_type t = (*pp_)[block_index];
        t &= ~(block_type)0 << prev % bits_per_block;
        if (t)
            return block_index * bits_per_block + First_bit<sizeof(t)>::find(t);
        return find_from(block_index + 1);
    }

    bool operator[](size_type pos) const
    {
        return get(pos);
    }

    bool equals(dynamic_bit_array<size_type, block_type> const& right) const
    {
        if (this->size_ != right.size_)
            return false;
        if (!this->size_)
            return true;
        return !memcmp(*this->pp_, *right.pp_, block_count() * sizeof(block_type));
    }

    template<class V>
    void dump(V& v)
    {
        for (size_type i = 0; i < size_; ++i)
        {
            v << (get(i) ? "1" : "0");
        }
    }

};

namespace meta
{

template<class X, class Y>
struct is_visitable< dynamic_bit_array<X, Y> >
{
    enum {result = 0};
};

}

//EOF!
